#include <stdio.h>

const int n = 10;                         // 集合容量
int s[] = {2, 3, 8, 9, 4, 7, 4, 3, 8, 9}; // 集合s
int t = 18;                               // t值

int x[n];         //临时解向量
int tmpValue = 0; //临时和

void backtrace(int traceNum, int **resultX)
{
    if (tmpValue > t)
    { // 剪枝函数
        return;
    }
    if (traceNum == n - 1) // 到达叶子节点
    {
        if (tmpValue == t)
        {
            for (int i = 0; i < n; i++)
            {
                (*resultX)[i] = x[i];
            }
        }
        return;
    }

    // 不加
    x[traceNum] = 0;
    backtrace(traceNum + 1, resultX);

    // 加
    x[traceNum] = 1;
    tmpValue += s[traceNum];
    backtrace(traceNum + 1, resultX);
    tmpValue -= s[traceNum];
}

int main()
{
    int *resultX = new int[n];
    backtrace(0, &resultX);
    for (int i = 0; i < n; i++)
    {
        printf("%-3d", resultX[i]);
    }
    printf("\n");
    delete[](resultX);
    return 0;
}